//思路：暴力搜索，还有kmp算法遗忘了


import java.util.*;

public class Solution {
    public static void main(String[] args) {

}
//暴力解
    public  int strStr(String haystack, String needle) {
        char[] c1=haystack.toCharArray();
        char[] c2=needle.toCharArray();
        for(int i=0;i<c1.length-c2.length;i++){
            int k=i;
            boolean flag=true;
            for (int j = 0; j < c2.length; j++) {
                if(c1[k++]!=c2[j]){
                    flag=false;
                }
            }
            if(flag) return i;
        }
        return -1;
    }
    //kmp算法
    public  int strstr1(String haystack, String needle) {
       int[] next=new int[needle.length()];
       getNext(next,needle);
       int j=0;
        for (int i = 0; i < haystack.length(); i++) {
            while(j>0&&haystack.charAt(i)!=needle.charAt(j)){
                j=next[j-1];
            }
           if(haystack.charAt(i)==needle.charAt(j)){
               j++;
           }
           if(j==needle.length()){
             return i-j+1;
           }
        }
           return -1;
    }
    public  void getNext(int[] next, String s){
        int j=0;
        next[0]=0;
        for (int i = 1; i < s.length(); i++) {
            //不等条件找前缀，为什么要用while,因为要不断回溯
            while(j>0&&s.charAt(i)!=s.charAt(j)){
                j=next[j-1];
            }
            if(s.charAt(i)==s.charAt(j)){
                j++;
            }
            next[i]=j;
        }
    }
    }













